package randomthoughts.dp;

/**
 * @author tongchen
 * @create 2023-04-12 23:20
 */
public class ClimbStairWithMinCost {
    public static void main(String[] args) {

    }

    /** leetcode 746
     * 五部曲：1.建立一维递归数组dp 下标i代表楼梯层数 dp[i]表示到达该层的最小花费2递推公式是dp[i]=Min(dp[i-1]+cost[i-1],dp[n-2]+cost[n-2])
     * 3.初始化，由于在0和1之前我们未踏上台阶，所以dp[0]=0,dp[1]=0;4.遍历顺序，因为前面推出后面，所以是从前往后推
     * @param cost
     * @return
     */
    public static int minCost(int[]cost,int n){
        //创建数组
        int[]dp= new int[n+1];
        dp[0]=0;
        dp[1]=0;
        //对dp进行遍历求解
        for(int i=2;i<=n;++i){
            dp[i]=Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
        }
        return dp[n];
    }
}
